package com.du.algorithm.primary;

import java.util.List;

/**
 * @Desc : 前缀树
 * @Author: shuangdu
 * @date : 2022/10/25
 */
public class PrefixTree {

    // 使用构造前缀树方法解决词根替换问题

    public static class TrieNode {
        private TrieNode[] child;
        private boolean isValid;

        public TrieNode() {
            // 字母有26个
            child = new TrieNode[26];
        }

        public TrieNode[] getChild() {
            return this.child;
        }

        public boolean isValid() {
            return this.isValid;
        }
    }

    /**
     * 初始化查找树
     * @param root 根
     * @param dic  词根
     */
    public void insert(TrieNode root, String dic) {
        TrieNode node = root;
        for (char c : dic.toCharArray()) {
            if (node.child[c - 'a'] == null) {
                node.child[c - 'a'] = new TrieNode();
            }
            node = node.child[c - 'a'];
        }
        node.isValid = true;
    }

    /**
     * 查找词根
     * @param root 查找树
     * @param word 单词
     * @return
     */
    public String searchMatch(TrieNode root, String word, boolean searchFirst) {
        TrieNode node = root;
        StringBuilder sb = new StringBuilder();
        for (char w : word.toCharArray()) {
            // 表示当前词根已查找完
            if (searchFirst && node.isValid) {
                break;
            }
            // 词根未匹配上
            if (node.child[w - 'a'] == null) {
                break;
            }
            // 否则继续往下查找
            node = node.child[w - 'a'];
            sb.append(w);
        }
        return sb.toString();
    }
    public String searchFirst(TrieNode root, String word, boolean searchFirst) {
        TrieNode node = root;
        StringBuilder sb = new StringBuilder();
        boolean match = true;
        for (char w : word.toCharArray()) {
            // 表示当前词根已查找完
            if (searchFirst && node.isValid) {
                break;
            }
            // 词根未匹配上
            if (node.child[w - 'a'] == null) {
                match = false;
                break;
            }
            // 否则继续往下查找
            node = node.child[w - 'a'];
            sb.append(w);
        }
        return match ? sb.toString() : word;
    }
    public boolean search(TrieNode node, String word) {
        for (char w : word.toCharArray()) {
            // 表示当前词根已查找完
            if (node.child[w - 'a'] != null || node.isValid) {
                return true;
            }
        }
        return false;
    }

    //-------------------------- [词根替换] ---------------------------------------//
    /**
     * 词根替换
     * @param dictionary
     * @param sentence
     * @return
     */
    public String replaceWords(List<String> dictionary, String sentence) {
        TrieNode root = new TrieNode();
        for (String dic : dictionary) {
            insert(root, dic);
        }

        String[] words = sentence.split(" ");
        String[] strs = new String[words.length];
        for (int i = 0; i<words.length; i++) {
            String word = words[i];
            strs[i] = searchFirst(root, word, true);
        }
        return String.join(" ", strs);
    }

}
